package Algorithm.Dp;
//https://leetcode-cn.com/problems/knight-probability-in-chessboard/
public class Leetcode_688_骑士在棋盘上的概率 {
    class Solution {
        public double knightProbability(int n, int k, int row, int column) {
            double[][][] dp = new double[k+1][n][n];

            int[][] v ={{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1}};

            for(int i = 0; i <= k; i++){
                for(int j = 0; j < n; j++){
                    for(int l = 0; l < n; l++){
                        if(i == 0){
                            dp[i][j][l] = 1;
                        }else{
                            for(int[] m : v){
                                if((j+m[0])>=0&&(j+m[0])<n&&(l+m[1])>=0&&(l+m[1])<n){
                                    dp[i][j][l] = dp[i][j][l] + dp[i-1][j+m[0]][l+m[1]] * 0.125;
                                }
                            }
                        }
                    }
                }
            }
            return dp[k][row][column];
        }
    }
}
